package com.leetcode.dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Leetcode797 {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        if (graph == null) {
            return res;
        }
        LinkedList<Integer> path = new LinkedList<>();
        dfs(graph, 0, path);
        return res;
    }

    private void dfs(int[][] graph, int index, LinkedList<Integer> path) {
        int[] currentNode = graph[index];
        // 输出 0 -> n-1 的节点
        if (!path.isEmpty() && path.getLast() == graph.length - 1) {
            res.add(new LinkedList<>(path));
            return;
        }

        for (int i = 0; i < currentNode.length; i++) {
            if (path.isEmpty()) {
                path.add(0);
            }
            path.add(currentNode[i]);
            dfs(graph, currentNode[i], path);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        // graph = [[1,2],[3],[3],[]]
        int[][] graph = {{1,2}, {3}, {3}, {}};
        Leetcode797 leet = new Leetcode797();
        List<List<Integer>> res = leet.allPathsSourceTarget(graph);
        System.out.println(res);
    }

}
